A computer system's responsiveness is constrained in three ways: by processor limitations, by communication limitations, and by memory limitations. Processor limitations have given way in accord with Moore's law, which holds that processor capability doubles every eighteen months. Communication limitations have given way in accord with recent increases in bandwidth provided by fiber optics and by advanced wireline techniques such as Asymmetric Digital Subscriber Loops.
Memory limitations, however, continue to be problematic. In practice, computer memory is often a mixed technology, with both solid-state and electromechanical aspects. Although the performance of solid-state memory has increased dramatically, its cost remains high relative to the need for such memory that has been created by the demands of the information age. Consequently, much computer memory continues to use electromechanical technology such as disk drives of various kinds.
Although such electromechanical technology offers vast storage capacity, its performance is not responsive. In turn the performance of a computer when used in an application such as Internet research may be limited by the time needed to read to and write from its large but slow electromechanical memory.
A longstanding solution to this problem is to use relatively slow memory for storing information whose recall does not directly limit the computer's responsiveness, and to use relatively fast memory for storing information that must be retrieved without perceptible delay. This principle is often carried one step further by dividing the fast memory itself into cache memory, which employs extraordinarily fast but expensive memory chips, and main memory, which uses somewhat slower but less expensive chips.
Because of the fast technology employed by the cache is expensive, the size of the cache must be limited. Consequently, in order to maximize the responsiveness of a computer system, the cache must be managed as efficiently as possible. Managing the cache efficiently is the purpose of a caching algorithm, which decides what information to add to the cache, what information to delete from the cache, and what information to keep in the main memory rather than in the cache.
One such algorithm is called the most-used caching algorithm. A most-used caching algorithm keeps information in the cache that has been used most often in the past, under the presumption that the information that has been used most often in the past will probably be the information that is needed next. Another such algorithm is the most-recently-used caching algorithm, which keeps information most recently used in the cache, under the presumption that the most recently used information will probably be the information that is needed next.
Unfortunately, these and other such caching algorithms are compromises that have significant limitations. For example, a most-used caching algorithm may be unreceptive to the need to cache new information when an Internet user's behavior changes. On the other hand, a most-recently-used algorithm may be too receptive to an Internet user's tangential excursions, and may suffer by discarding information needed long-term in favor of information used only once.
Thus, in view of the shortcomings of known caching algorithms, and in view of the importance of efficient cache management given the demands of the Internet and information age, there remains a need for a way of managing cache memory that draws upon the advantages of each of the various kinds of caching algorithms and yet minimizes their shortcomings.